#include<stdio.h>
#include<stdlib.h>
#define HEIGHT(node) ((node==NULL) ? 0 :(((AvarageTree*)(node))->height))
#define MAX(a,b) ((a)>(b)?(a):(b))


typedef struct avarageTree
{
    int num;
    struct avarageTree * left;
    struct avarageTree * right;
    int height;

}AvarageTree;

int getHeight(AvarageTree * node);
AvarageTree * create(int num,AvarageTree * left, AvarageTree * right);


AvarageTree * insertNode(AvarageTree * tree,int num);

void postOrder(AvarageTree * root);

//LL旋转的代码
static AvarageTree * left_left_rotation(AvarageTree * tree){
    AvarageTree * t1 = tree->left;
    tree->left = t1->right;
    t1->right = tree;
    tree->height = MAX(getHeight(tree->left),getHeight(tree->right)) + 1;
    t1->height = MAX(getHeight(t1->left),getHeight(t1->right))+1;
    return t1;
}

//RR旋转的代码
static AvarageTree * right_right_rotation(AvarageTree * tree){
    AvarageTree * t1 = tree->right;
    tree->right = t1->left;
    t1->left = tree;
    tree->height = MAX(getHeight(tree->left),getHeight(tree->right)) + 1;
    t1->height = MAX(getHeight(t1->left),getHeight(t1->right))+1;
    return t1;
}

//LR旋转的代码
static AvarageTree * left_right_rotation(AvarageTree * tree){
    tree->left = right_right_rotation(tree->left);
    tree = left_left_rotation(tree);
    return tree;
}

//RL旋转的代码
static AvarageTree * right_left_rotation(AvarageTree * tree){
    tree->right = left_left_rotation(tree->right);
    tree = right_right_rotation(tree);
    return tree;
}


int main(){

    AvarageTree * root = create(3,NULL,NULL);
    root = insertNode(root,1);
    root = insertNode(root,2);
    root = insertNode(root,4);
    root = insertNode(root,5);
    root = insertNode(root,6);
    printf("根：%d\n",root->num);
    printf("根：%d\n",root->right->num);
    
}

AvarageTree * create(int num,AvarageTree * left, AvarageTree * right){

    AvarageTree * node = (AvarageTree*)malloc(sizeof(AvarageTree));
    if(node==NULL){
        return NULL;
    }
    node->num = num;
    node->left = left;
    node->right = right;
    node->height = 0;

    return node;
}

int getHeight(AvarageTree * node){

    return HEIGHT(node);
}

AvarageTree * insertNode(AvarageTree * tree,int num){
    if(tree==NULL){
        AvarageTree * node = create(num,NULL,NULL);
        tree = node;
    }else if(num < tree->num){
        tree->left = insertNode(tree->left,num);

        int flag = HEIGHT(tree->left) - HEIGHT(tree->right) ;
        if(flag == 2){
            if(num <  tree->left->num){
                tree = left_left_rotation(tree);
            }else{
                tree = left_right_rotation(tree);
            }
        }
    }else{
        tree->right = insertNode(tree->right,num);

        int flag = getHeight(tree->right) - getHeight(tree->left);
        if(flag == 2){
            if(num > tree->right->num){
                tree = right_right_rotation(tree);
            }else{
                tree = right_left_rotation(tree);
            }
        }
    }
    tree->height = MAX(getHeight(tree->left),getHeight(tree->right)) + 1;

    return tree;
}